#define _CRT_SECURE_NO_WARNINGS 1

#include "HeapSort.h"

void test()
{
	int arr[] = { 5, 3, 8, 1, 12, 6, 9, 8, 4, 5, 3 };
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		std::cout << arr[i] << " ";
	}
	std::cout << std::endl;
}

int main()
{
	test();
	return 0;
}

class Solution {
public:
    int numSquares(int n)
    {
        int m = sqrt(n);
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int j = 1; j <= n; j++) dp[0][j] = 0x3f3f3f3f;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - i * i >= 0) dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        }
        return dp[m][n];
    }
};
class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = nums[0], g[0] = 0;
        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};
class Solution {
public:
    vector<vector<int>> generate(int n)
    {
        vector<vector<int>> dp(n);
        for (int i = 0; i < n; i++)
        {
            dp[i].resize(i + 1, 0);
            dp[i][0] = dp[i][i] = 1;
        }
        for (int i = 2; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (dp[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        return dp;
    }
};
class Solution {
public:
    int climbStairs(int n)
    {
        if (n == 1 || n == 2) return n;
        vector<int> dp(n);
        dp[0] = 1, dp[1] = 2;
        for (int i = 2; i < n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
};
class Solution {
public:
    vector<int> partitionLabels(string s)
    {
        vector<int> hash(27);
        for (int i = 0; i < s.size(); i++) hash[s[i] - 'a'] = i;
        vector<int> ret;
        int left = 0, right = 0;
        for (int i = 0; i < s.size(); i++)
        {
            right = max(right, hash[s[i] - 'a']);
            if (i == right)
            {
                ret.push_back(right - left + 1);
                left = right + 1;
            }
        }
        return ret;
    }
};
class Solution {
public:
    int jump(vector<int>& nums)
    {
        int left = 0, right = 0, maxpos = 0, ret = 0, n = nums.size();
        while (left <= right)
        {
            if (maxpos >= n - 1) return ret;
            for (int i = left; i <= right; i++)
            {
                maxpos = max(maxpos, i + nums[i]);
            }
            left = right + 1, right = maxpos;
            ret++;
        }
        return -1;
    }
};
class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        int left = 0, right = 0, maxpos = 0, n = nums.size();
        while (left <= right)
        {
            if (maxpos >= n - 1) return true;
            for (int i = left; i <= right; i++)
            {
                maxpos = max(maxpos, i + nums[i]);
            }
            left = right + 1;
            right = maxpos;
        }
        return false;
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int MIN = prices[0];
        int ret = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] - MIN > ret) ret = prices[i] - MIN;
            if (prices[i] < MIN) MIN = prices[i];
        }
        return ret;
    }
};